import java.util.*;

public class Dijkstra {

    // 图的邻接矩阵
    private int[][] graph;
    // 图中节点的可达节点
    private List<Integer>[] adj;

    private Dijkstra() {

    }

    /**
     * 从图中一点到一个点的距离
     * @param from 从
     * @param to 至
     * @return 距离
     */
    private int weight(int from, int to) {
        return graph[from][to];
    }


    public Dijkstra(int[][] graph) {
        this.graph = graph;
        int l = graph.length;
        // 初始化，通过图数据构造邻接链表
        this.adj = new List[l];
        for (int i = 0; i < l; i++) {
            List<Integer> curAdj = new ArrayList<>();
            for (int j = 0; j < l; j++) {
                if (graph[i][j] != Integer.MAX_VALUE) {
                    curAdj.add(j);
                }
            }
            adj[i] = curAdj;
        }

    }

    public List<Integer> adj(int s) {
        return adj[s];
    }

    int[] dijkstra(int start) {
        // 图中节点的个数
        int V = graph.length;
        // 记录最短路径的权重，你可以理解为 dp table
        // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
        int[] distTo = new int[V];
        // 求最小值，所以 dp table 初始化为正无穷
        Arrays.fill(distTo, Integer.MAX_VALUE);
        // base case，start 到 start 的最短距离就是 0
        distTo[start] = 0;

        // 优先级队列，distFromStart 较小的排在前面
        Queue<State> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.distFromStart));

        // 从起点 start 开始进行 BFS
        pq.offer(new State(start, 0));

        while (!pq.isEmpty()) {
            State curState = pq.poll();
            int curNodeID = curState.id;
            int curDistFromStart = curState.distFromStart;

            if (curDistFromStart > distTo[curNodeID]) {
                // 已经有一条更短的路径到达 curNode 节点了
                continue;
            }
            // 将 curNode 的相邻节点装入队列
            for (int nextNodeID : adj(curNodeID)) {
                // 看看从 curNode 达到 nextNode 的距离是否会更短
                int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
                if (distTo[nextNodeID] > distToNextNode) {
                    // 更新 dp table
                    distTo[nextNodeID] = distToNextNode;
                    // 将这个节点以及距离放入队列
                    pq.offer(new State(nextNodeID, distToNextNode));
                }
            }
        }
        return distTo;
    }

    private static class State {
        // 图节点的 id
        int id;
        // 从 start 节点到当前节点的距离
        int distFromStart;

        State(int id, int distFromStart) {
            this.id = id;
            this.distFromStart = distFromStart;
        }
    }


    public static void main(String[] args) {
        int[][] graph = {
                {0, 7, 12, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, 0, 2, 9, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 1},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 0, 5},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };
        Dijkstra dijkstra = new Dijkstra(graph);
        int[] dijkstra1 = dijkstra.dijkstra(0);
        System.out.println(Arrays.toString(dijkstra1));
    }

}
